270. Closest Binary Search Tree Value
Easy

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

 

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 0 <= Node.val <= 109
  • -109 <= target <= 109
Accepted
195,666
Submissions
383,891
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.32 (38 votes)

Premium

Solution


Approach 1: Recursive Inorder + Linear search, O(N) time

Intuition

The simplest approach (3 lines in Python) is to build inorder traversal and then find the closest element in a sorted array with built-in function min.

pic

This approach is simple stupid, and serves to identify the subproblems.

Algorithm

  • Build an inorder traversal array.

  • Find the closest to target element in that array.

Implementation

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) because to build inorder traversal and then to perform linear search takes linear time.
  • Space complexity : O(N)\mathcal{O}(N) to keep inorder traversal.


Approach 2: Iterative Inorder, O(k) time

Intuition

Let's optimise Approach 1 in the case when index k of the closest element is much smaller than the tree heigh H.

First, one could merge both steps by traversing the tree and searching the closest value at the same time.

Second, one could stop just after identifying the closest value, there is no need to traverse the whole tree. The closest value is found if the target value is in-between of two inorder array elements nums[i] <= target < nums[i + 1]. Then the closest value is one of these elements.

pic

Algorithm

  • Initiate stack as an empty array and predecessor value as a very small number.

  • While root is not null:

    • To build an inorder traversal iteratively, go left as far as you can and add all nodes on the way into stack.

    • Pop the last element from stack root = stack.pop().

    • If target is in-between of pred and root.val, return the closest between these two elements.

    • Set predecessor value to be equal to root.val and go one step right: root = root.right.

  • We're here because during the loop one couldn't identify the closest value. That means that the closest value is the last value in the inorder traversal, i.e. current predecessor value. Return it.

Implementation

Complexity Analysis

  • Time complexity : O(k)\mathcal{O}(k) in the average case and O(H+k)\mathcal{O}(H + k) in the worst case, where k is an index of closest element. It's known that average case is a balanced tree, in that case stack always contains a few elements, and hence one does 2k2k operations to go to kth element in inorder traversal (k times to push into stack and then k times to pop out of stack). That results in O(k)\mathcal{O}(k) time complexity. The worst case is a completely unbalanced tree, then you first push H elements into stack and then pop out k elements, that results in O(H+k)\mathcal{O}(H + k) time complexity.

pic

  • Space complexity : up to O(H)\mathcal{O}(H) to keep the stack in the case of non-balanced tree.


Approach 3: Binary Search, O(H) time

Intuition

Approach 2 works fine when index k of closest element is much smaller than the tree height H.

Let's now consider another limit and optimise Approach 1 in the case of relatively large k, comparable with N.

Then it makes sense to use a binary search: go left if target is smaller than current root value, and go right otherwise. Choose the closest to target value at each step.

pic

Kudos for this solution go to @stefanpochmann.

Implementation

Complexity Analysis

  • Time complexity : O(H)\mathcal{O}(H) since here one goes from root down to a leaf.

  • Space complexity : O(1)\mathcal{O}(1).

Report Article Issue

Comments: 27
sriharik's avatar
Read More

Can someone explain why approach #3 is O(H)? Wouldn't it be Log N in runtime since we are omitting half the tree each iteration?

29
Show 6 replies
Reply
Share
Report
warlocx's avatar
Read More

For solution #3 , should we return or break when target==root.val. Wont that save the further iterations?

7
Show 2 replies
Reply
Share
Report
novice87's avatar
Read More

For the first solution, i think it would be better to use buillt in Double.compare method in Java instead of deciding 1, -1
return Double.compare(Math.abs(o1 - target), Math.abs(o2 - target));

or even better using Java 8+
Collections.min(list, Comparator.comparingDouble(o -> Math.abs(o - target)));

This will also take care of returning 0 in case of equal values.

5
Reply
Share
Report
zestypotato's avatar
Read More

closest = min(root.val, closest, key = lambda x: abs(target - x))
root = root.left if target < root.val else root.right

Interesting way to write it. I thought this was difficult to read (took me a minute to realize it was essentially the same as my solution). Unless there's a code golf competition, I'd rather just write it out fully. Same with the tertiary statements in #1.

cur = root
...
closest = min(abs(target-cur.val), abs(target-closest))
if target < cur.val:
    cur = cur.left
else:
    cur = cur.right

1
Show 1 reply
Reply
Share
Report
Yunxiang-Li's avatar
Read More

Hi guys, Why approach #2 's time complexity is O(h) but not O(N) where n indicates the amount of nodes?
I mean if the last TreeNode's value is the closest, the bottom right one, why the time complexity is not O(N) since we have to loop until the last element.

1
Reply
Share
Report
user8367d's avatar
Read More

public int closestValue(TreeNode root, double target) {
    if (root == null) return -1;

    int res = root.val > target ? closestValue(root.left, target): closestValue(root.right, target);
    
    if (res == -1) return root.val;
    return Math.abs(root.val - target) > Math.abs(res - target) ? res : root.val;
}

1
Reply
Share
Report
Bll's avatar
Read More

If I understand the problem description correctly, shown approach 3 is not correct. we care about te absolute difference between target and tree node values, if we go into left subtree just because target is smaller than the root node, then we might be missing a node in the right subtree that could have much smaller abs difference.

-12
Show 6 replies
Reply
Share
Report
LeetCodeSuperman's avatar
Read More

class Solution
{
    private Double val = null;
    
    public int closestValue(TreeNode root, double target)
    {
        if (root == null)
        {
            return val.intValue();
        }
        Double currVal = Double.valueOf(root.val);
        if (currVal == target)
        {
            return currVal.intValue();
        }
        if (val == null || Math.abs(val - target) > Math.abs(currVal - target))
        {
            val = currVal;
        }
        return closestValue(currVal > target ? root.left : root.right, target);
    }
}

0
Reply
Share
Report
nix_on's avatar
Read More

complexity of algo 2 is always O(H) I think. Because with the first traversal loop you always reach a leaf, thus you do around H steps if the tree is balanced

0
Show 1 reply
Reply
Share
Report
zoomden's avatar
Read More

For Approach 3 can't we further elaborate on the time complexity and say that in the case of a balanced tree we will have time complexity O(logN) since O(logN) == O(H) and in unbalanced tree the worst case would be O(N) since the tree's height would equal number of nodes (worst case). Let me know what you think?

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.